module(..., package.seeall)
-- math.randomseed(os.time())
local json = require("json")
local model = {}

function initModel()
	model = {
		ModelData = {
			tMapRecoder = {},
			maxDeep = 100000,
			mapWidth = nil,
			mapHeight = nil,
			beginX = 1,
			beginY = 1,
			endX = 1,
			endY = 1,
			tOpenList = {
				-- total = 2*mapWidth - (1 + 1) + 1, 总的值
				-- now = 1, -- 当前值
				-- parent = {nil, nil}, -- 父亲节点
			},
			tCloseList = {
				-- 闭合列表，在此列表中的元素将不再考虑范围之内
				-- 格式同tOpenList
			},
			tSortedList = {
				-- [totalDeep] = {
					-- [1] = {
							-- [1] = x, [2] = y
					-- },
					-- ...
				-- }
			},
		}
	}

	function model.getModelData(key)
		return model.ModelData[key]
	end

	function model.setModelData(key, value)
		model.ModelData[key] = value
	end
end


-- 获取路径
local function getWay()
	local beginX = model.getModelData("beginX")
	local beginY = model.getModelData("beginY")

	local endX = model.getModelData("endX")
	local endY = model.getModelData("endY")

	local tCloseList = model.getModelData("tCloseList")

	local tRecoder = {}

	local posX, posY = endX, endY


	while(true) do
		tRecoder[#tRecoder + 1] = {posX, posY}

		posX, posY = tCloseList[posX][posY].parent[1], tCloseList[posX][posY].parent[2]

		if not posX or not posY then
			break
		end
	end

	local tResult = {}
	for i = #tRecoder, 1, -1 do
		tResult[#tResult + 1] = tRecoder[i]
	end

	return tResult
end

-- 获取预期值
local function getExpect(x, y)
	local endX = model.getModelData("endX")
	local endY = model.getModelData("endY")
	return math.abs(endX - x) + math.abs(endY - y)
end


-- 算法使用最基础的冒泡排序，在数量变大的时候会卡顿
local function getBest()
	local tSortedList = model.getModelData("tSortedList")
	local x, y

	local maxDeep = model.getModelData("maxDeep")
	local minTotal = maxDeep

	for total, v in pairs(tSortedList) do
		if #v ~= 0 then
			if total < minTotal then
				minTotal = total
			end
		end
	end
	if minTotal ~= maxDeep then
		x, y = tSortedList[minTotal][1][1], tSortedList[minTotal][1][2]
	end

	return x, y
end

------------------- openList ---------------------
function deleteElementInOpenList(x, y)
	local tOpenList = model.getModelData("tOpenList")

	if not tOpenList[x] then
		return false
	end

	tOpenList[x][y] = nil
end

function addElementToOpenList(x, y, parentX, parentY, isTtilted)
	local tOpenList = model.getModelData("tOpenList")
	tOpenList[x] = tOpenList[x] or {}

	if not parentX or not parentY then
		tOpenList[x][y] = {
			now = 1,
			total = getExpect(x, y) + 1,
			parent = {nil, nil}
		}
	else
		local tCloseList = model.getModelData("tCloseList")
		local now
		if isTtilted then
			now = tCloseList[parentX][parentY].now + 1.4
		else
			now = tCloseList[parentX][parentY].now + 1
		end
		local expect = getExpect(x, y)
		local total = now + expect

		tOpenList[x][y] = {
			now = now,
			total = total,
			parent = {parentX, parentY}
		}
	end
end

---------------------- sortedList ----------------
-- 添加元素
function addElementToSortedList(x, y)
	local tOpenList = model.getModelData("tOpenList")
	local tSortedList = model.getModelData("tSortedList")
	local total = tOpenList[x][y].total

	tSortedList[total] = tSortedList[total] or {}

	tSortedList[total][#tSortedList[total] + 1] = {x, y}
end

-- 删除元素
function deleteElementInSortedList(x, y)
	local tSortedList = model.getModelData("tSortedList")
	local tOpenList = model.getModelData("tOpenList")

	local total = tOpenList[x][y].total

	if not tSortedList[total] then
		return
	end

	for index, v in pairs(tSortedList[total]) do
		if x == v[1] and y == v[2] then
			-- 元素移动
			table.remove(tSortedList[total], index)
			break
		end
	end

	if #tSortedList[total] == 0 then
		tSortedList[total] = nil
	end
end

---------------- closeList -------------------
local function addElementToCloseList(x, y, isNotReachAble)
	local tCloseList = model.getModelData("tCloseList")
	local tOpenList = model.getModelData("tOpenList")

	tCloseList[x] = tCloseList[x] or {}

	if not isNotReachAble then
		if tOpenList[x] and tOpenList[x][y] then
			tCloseList[x][y] = tOpenList[x][y]
		end
	else
		local maxDeep = model.getModelData("maxDeep")
		 tCloseList[x][y] = {
			now = maxDeep,
			total = maxDeep,
			parent = {nil, nil}
		}
	end
end

--[[补全当前x y的相关信息
	isTtilted 是否倾斜
]]

local function addToMap(x, y, parentX, parentY, isTtilted)
	local mapWidth = model.getModelData("mapWidth")
	local mapHeight = model.getModelData("mapHeight")
	local tCloseList = model.getModelData("tCloseList")
	local tOpenList = model.getModelData("tOpenList")
	local tMapRecoder = model.getModelData("tMapRecoder")

	-- 边界检测
	if x <= 0 or x > mapWidth or y <= 0 or y > mapHeight then
		return
	end

	-- 重复检查路径
	if (tCloseList[x] and tCloseList[x][y]) then
		return
	end

	-- 此路径不可达
	if tMapRecoder[x][y] == 0 then
		addElementToCloseList(x, y, true)
		return
	end

	local now = tCloseList[parentX][parentY].now
	if isTtilted then
		now = now + 1.4
	else
		now = now + 1
	end

	local expect = getExpect(x, y)
	local total = now + expect

	if (tOpenList[x] and tOpenList[x][y]) then
		if total < tOpenList[x][y].total then
			-- 删除旧的存储位置
			deleteElementInSortedList(x, y)
			deleteElementInOpenList(x, y)

			addElementToOpenList(x, y, parentX, parentY, isTtilted)
			addElementToSortedList(x, y)
		else

		end
	else
		tOpenList[x] = tOpenList[x] or {}

		addElementToOpenList(x, y, parentX, parentY, isTtilted)
		addElementToSortedList(x, y)
	end
end

-- 创建A星寻路后的地图
local function aStarMap(x, y)

	addElementToCloseList(x, y)

	deleteElementInSortedList(x, y)
	deleteElementInOpenList(x, y)

	-- 调整添加的位置将会调整寻路的先后顺序
	-- 右
	addToMap(x + 1, y, x, y)
	-- 下
	addToMap(x, y + 1, x, y)
	-- 右下
	addToMap(x + 1, y + 1, x, y, true)
	
	-- 右上
	addToMap(x + 1, y - 1, x, y, true)
	-- 上
	addToMap(x, y - 1, x, y)
	-- 左
	addToMap(x - 1, y, x, y)
	-- 左下
	addToMap(x - 1, y + 1, x, y, true)
	-- 左上
	addToMap(x - 1, y - 1, x, y, true)

	local nextX, nextY = getBest()

	if not nextX or not nextY then
		return false
	end

	local endX, endY = model.getModelData("endX"), model.getModelData("endY")
	if nextX == endX and nextY == endY then
		addElementToCloseList(nextX, nextY)
		return true
	end

	return aStarMap(nextX, nextY)
end

function initMap()
	local beginX = model.getModelData("beginX")
	local beginY = model.getModelData("beginY")

	addElementToOpenList(beginX, beginY, nil, nil)

	addElementToSortedList(beginX, beginY)
end

-- 打印地图
local function printMap(tMapRecoder)
	for i = 1, #tMapRecoder do
		print(table.concat(tMapRecoder[i], " "))
	end
end

-- 外部调用
function doAStar(convertParams)
	initModel()

	local beginX, beginY = convertParams.beginX, convertParams.beginY

	model.setModelData("tMapRecoder", convertParams.tMapRecoder)
	model.setModelData("mapWidth", #convertParams.tMapRecoder)
	model.setModelData("mapHeight", #convertParams.tMapRecoder[1])

	model.setModelData("beginX", beginX)
	model.setModelData("beginY", beginY)

	model.setModelData("endX", convertParams.endX)
	model.setModelData("endY", convertParams.endY)

	initMap()

	local beginTime = system.getTimer()
	local isBestWay = aStarMap(beginX, beginY)
	local endTime = system.getTimer()

	print("lastTime", endTime - beginTime, isBestWay)

	if isBestWay then
		local tResult = getWay()
		print(json.encode(tResult))
		return tResult, "sucess"
		
	else
		return nil, "can no find the bestWay"
	end
end

-- 模块自测试
function AStarTest()
	local mapWidth = 100
	local mapHeight = 100
	--[[创建地图
		创建一个地图
		O 代表可以走的路径
		X 代表不能走的路径
	--]]
	local function createMap()
		local tMapRecoder = {}
		for i = 1, mapWidth do
			tMapRecoder[i] = {}
			for j = 1, mapHeight do
				local isReachable = math.random(0, 3)
				if (i == 1 and j == 1) or (i == mapWidth and j == mapHeight) then
					tMapRecoder[i][j]= 1
				elseif isReachable == 0 then
					tMapRecoder[i][j] = 0
				else
					tMapRecoder[i][j] = 1
				end
			end
		end

		return tMapRecoder
	end

	doAStar({
		tMapRecoder = createMap(),
		beginX = 1,
		beginY = 1,
		endX = mapWidth,
		endY = mapHeight,
	})
end
